package T41_T50;


import datastructure.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//思路：BFS（广度优先）算法
//1 将每一层结点存入队列并记录每一层节点个数
//2 每次从队列首部取出每一层的结点存入结果res中
public class T41 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root==null)return new ArrayList<>();
        ArrayList<List<Integer>> res = new ArrayList<>();
        //存放/取出结点的队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //存放每一层结点的链表
            List<Integer> level = new ArrayList<>();
            int size=queue.size();
            /*这里如果将queue.size()直接放入循环条件会无法正确遍历
            * 因为在循环体内进行了出队操作，queue.size()会动态变化*/
            for (int i = 0; i < size; i++) {
                //从队列中取出每层的结点
                TreeNode polled = queue.poll();
                //将取出的结点存入level中
                level.add(polled.val);
                //如果当前节点有子结点，将他们存入queue队列
                if (polled.left!=null)queue.offer(polled.left);
                if (polled.right!=null)queue.offer(polled.right);
            }
            //将level存储的结点存入res中
            res.add(level);
        }
        return res;
    }
}
